package tree;

import offer.TreeNode;

/**
 * 给你一棵以root为根的二叉树，请你返回 任意二叉搜索子树的最大键值和。
 *
 * 二叉搜索树的定义如下：
 *
 * 任意节点的左子树中的键值都小于此节点的键值。
 * 任意节点的右子树中的键值都 大于此节点的键值。
 * 任意节点的左子树和右子树都是二叉搜索树。
 *
 */
public class leetCode1373_maxSumBST {

    int ans = 0 ;
    public int maxSumBST(TreeNode root) {
        build(root);
        return ans;
    }

    /**
     * res[0] 记录以 root 为根的二叉树是否是 BST，若为 1 则说明是 BST，若为 0 则说明不是 BST；
     *
     * res[1] 记录以 root 为根的二叉树所有节点中的最小值；
     *
     * res[2] 记录以 root 为根的二叉树所有节点中的最大值；
     *
     * res[3] 记录以 root 为根的二叉树所有节点值之和。
     * @param root
     * @return
     */
    public int[] build(TreeNode root){
        if(root == null){
            return new int[]{1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        }
        int[] left = build(root.left);
        int[] right = build(root.right);

        int[] res = new int[4];
        if(left[0] == 1
                && right[0] == 1
                && left[2] < root.val
                && right[1] > root.val ){
            res[0] = 1;
            res[1] = Math.min(root.val,left[1]);
            res[2] = Math.max(root.val,right[2]);
            res[3] = left[3] + right[3] + root.val;
            ans = Math.max(ans,res[3]);
        }
        return res;

    }
}











